{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #minimum-spanning-tree #sorting #strongly-connected-component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #最小生成树 #排序 #强连通分量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCriticalAndPseudoCriticalEdges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最小生成树里的关键边和伪关键边"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code>&nbsp;个点的带权无向连通图，节点编号为 <code>0</code>&nbsp;到 <code>n-1</code>&nbsp;，同时还有一个数组 <code>edges</code>&nbsp;，其中 <code>edges[i] = [from</code><code><sub>i</sub>, to<sub>i</sub>, weight<sub>i</sub>]</code>&nbsp;表示在&nbsp;<code>from<sub>i</sub></code>&nbsp;和&nbsp;<code>to<sub>i</sub></code>&nbsp;节点之间有一条带权无向边。最小生成树&nbsp;(MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。</p>\n",
    "\n",
    "<p>请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。</p>\n",
    "\n",
    "<p>请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/21/ex1.png\" style=\"height: 262px; width: 259px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]\n",
    "<strong>输出：</strong>[[0,1],[2,3,4,5]]\n",
    "<strong>解释：</strong>上图描述了给定图。\n",
    "下图是所有的最小生成树。\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/21/msts.png\" style=\"height: 553px; width: 540px;\">\n",
    "注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。\n",
    "边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/21/ex2.png\" style=\"height: 253px; width: 247px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]\n",
    "<strong>输出：</strong>[[],[0,1,2,3]]\n",
    "<strong>解释：</strong>可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= min(200, n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub> &lt; to<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>1 &lt;= weight<sub>i</sub>&nbsp;&lt;= 1000</code></li>\n",
    "\t<li>所有 <code>(from<sub>i</sub>, to<sub>i</sub>)</code>&nbsp;数对都是互不相同的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree](https://leetcode.cn/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree](https://leetcode.cn/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]', '4\\n[[0,1,1],[1,2,1],[2,3,1],[0,3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "      parent=list(range(n))\n",
    "      def find(index):\n",
    "          if index!=parent[index]:\n",
    "              parent[index] = find(parent[index])\n",
    "          return parent[index]\n",
    "\n",
    "      sorted_edges = sorted(edges, key=lambda x:x[-1])\n",
    "      total = 0\n",
    "      for x,y,w in sorted_edges:\n",
    "          rx, ry = find(x), find(y)\n",
    "          if rx!=ry:\n",
    "              parent[rx] = ry\n",
    "              total+=w\n",
    "      key_edge=[]  \n",
    "      no_key_edge=[] \n",
    "      for i,edge in enumerate(edges):\n",
    "          cx,cy,cw = edge\n",
    "          tmp_edges = edges[:i]+edges[i+1:]\n",
    "          parent=list(range(n))\n",
    "          parent[cx]=cy\n",
    "\n",
    "          sorted_edges = sorted(tmp_edges, key=lambda x:x[-1])\n",
    "          total1 = cw\n",
    "          for x,y,w in sorted_edges:\n",
    "              rx, ry = find(x), find(y)\n",
    "              if rx!=ry:\n",
    "                  parent[rx] = ry\n",
    "                  total1+=w\n",
    "          if total1>total:\n",
    "              continue\n",
    "\n",
    "          parent=list(range(n))\n",
    "          total2 = 0\n",
    "          for x,y,w in sorted_edges:\n",
    "              rx, ry = find(x), find(y)\n",
    "              if rx!=ry:\n",
    "                  parent[rx] = ry\n",
    "                  total2+=w\n",
    "          if total!=total2:\n",
    "              key_edge.append(i)\n",
    "          else:\n",
    "              no_key_edge.append(i)\n",
    "      return [key_edge,no_key_edge]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n \n",
    "\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "\n",
    "    def clear(self) -> bool:\n",
    "        for i in range(len(self.parent)):\n",
    "            self.parent[i] = i\n",
    "            self.rank[i] = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(\n",
    "        self, n: int, edges: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "\n",
    "        # 1. 使用 Kruskal 算法求\n",
    "        #   - 最小生成树权值和 mstws\n",
    "        #   - 构成最小生成树的权值集合 wset\n",
    "        mstws, cnt = 0, 1\n",
    "        wset = set()\n",
    "\n",
    "        ufs = UnionFindSet(n)\n",
    "\n",
    "        for u, v, w in sorted(edges, key=lambda e: e[2]):\n",
    "            if ufs.find(u) != ufs.find(v):\n",
    "                ufs.union(u, v)\n",
    "                wset.add(w)\n",
    "                mstws += w\n",
    "\n",
    "                cnt += 1\n",
    "                if cnt == n:\n",
    "                    break\n",
    "\n",
    "        # 2. 求出关键边和伪关键边候选集合\n",
    "        candset = set()\n",
    "        for i, edge in enumerate(edges):\n",
    "            if edge[-1] in wset:\n",
    "                candset.add(i)\n",
    "\n",
    "        # 3. 从候选集合中找出所有的关键边和伪关键边\n",
    "        critical, pseudo = [], []\n",
    "        for idx in candset:\n",
    "            # 1. 使用 Kruskal 算法判断第 idx 条边是否为关键边\n",
    "\n",
    "            edges_sorted = sorted([\n",
    "                edge for i, edge in enumerate(edges) if i != idx\n",
    "            ], key=lambda e: e[2])\n",
    "            \n",
    "            ufs.clear()\n",
    "            # ufs = UnionFindSet(n)\n",
    "\n",
    "            vals, cnt = 0, 1\n",
    "            for u, v, w in edges_sorted:\n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "                    vals += w\n",
    "\n",
    "                    cnt += 1\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "            \n",
    "            # 第 idx 条边为关键边\n",
    "            if cnt < n or vals > mstws:\n",
    "                critical.append(idx)\n",
    "                continue\n",
    "\n",
    "            # 2. 判断第 idx 条边是否为伪关键边\n",
    "\n",
    "            ufs.clear()\n",
    "            # ufs = UnionFindSet(n)\n",
    "\n",
    "            ufs.union(edges[idx][0], edges[idx][1])\n",
    "            vals, cnt = edges[idx][2], 2\n",
    "            \n",
    "            for u, v, w in edges_sorted:\n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "                    vals += w\n",
    "\n",
    "                    cnt += 1\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "            \n",
    "            if vals == mstws:\n",
    "                pseudo.append(idx)\n",
    "\n",
    "        return [critical, pseudo]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        #### kruskal\n",
    "\n",
    "        def kruskal(n, edges, remove = -1, add = -1):\n",
    "            parent = [i for i in range(n)]\n",
    "            def find(node):\n",
    "                while parent[node] != node:\n",
    "                    node = parent[node]\n",
    "                return node\n",
    "\n",
    "            def union(p, q):\n",
    "                root_p = find(p)\n",
    "                root_q = find(q)\n",
    "\n",
    "                if root_p != root_q:\n",
    "                    parent[root_p] = root_q\n",
    "                    return True\n",
    "\n",
    "                return False\n",
    "            cost = 0\n",
    "            import heapq\n",
    "            edge_q = []\n",
    "            connected = set()\n",
    "            for i, e in enumerate(edges):\n",
    "                if i== remove:\n",
    "                    continue\n",
    "                elif i == add:\n",
    "                    cost += e[2]\n",
    "                    connect = union(e[0], e[1])\n",
    "                    connected.add(i)\n",
    "                    continue\n",
    "                heapq.heappush(edge_q, [e[2], e[0], e[1], i])\n",
    "            \n",
    "            \n",
    "            while len(edge_q):\n",
    "                e = heapq.heappop(edge_q)\n",
    "                connect = union(e[1], e[2])\n",
    "                if connect:\n",
    "                    cost += e[0]\n",
    "                    connected.add(e[3])\n",
    "\n",
    "\n",
    "            \n",
    "            return cost, connected\n",
    "\n",
    "        min_cost, _ = kruskal(n, edges)\n",
    "\n",
    "        import copy\n",
    "        key_edges = []\n",
    "        left_edges = []\n",
    "        for i in range(len(edges)):\n",
    "            cost, connected = kruskal(n, edges, remove=i)\n",
    "            if len(connected) < n-1 or cost  > min_cost:\n",
    "                key_edges.append(i)\n",
    "            else:\n",
    "                cost, connected = kruskal(n, edges, add = i)\n",
    "                if cost == min_cost:\n",
    "                    left_edges.append(i)\n",
    "            \n",
    "\n",
    "        return [key_edges, left_edges]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for (i, edge) in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for edge in edges:\n",
    "            if uf_std.unite(edge[0], edge[1]):\n",
    "                value += edge[2]\n",
    "\n",
    "        ans = [[], []]\n",
    "        for i in range(m):\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        edges = [[i]+v for i,v in enumerate(edges)]\n",
    "        edges.sort(key=lambda x:x[-1])\n",
    "\n",
    "        p={i:i for i in range(n)}\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "      \n",
    "        def ksk(edg):\n",
    "            p={i:i for i in range(n)}\n",
    "            ans=0\n",
    "            for ind,s,e,d in edg:\n",
    "                a=find(s)\n",
    "                b=find(e)\n",
    "                if a!=b:\n",
    "                    ans=ans+d\n",
    "                    union(s,e)\n",
    "            return ans\n",
    "        good=[]\n",
    "        bad=[]\n",
    "        st=ksk(edges)\n",
    "     \n",
    "        for i in range(len(edges)):\n",
    "            ind,cs,ce,cw =edges[i]\n",
    "            p={j:j for j in range(n)}\n",
    "            union(cs,ce)\n",
    "            newe=edges[:i]+edges[i+1:]\n",
    "            x=ksk(newe)+cw\n",
    "            if st!=x:\n",
    "                continue\n",
    "            p={j:j for j in range(n)}\n",
    "            y=ksk(newe)\n",
    "            if st==y:\n",
    "                bad.append(ind)\n",
    "            else:\n",
    "                good.append(ind)\n",
    "        res=[]\n",
    "        res.append(good)\n",
    "        res.append(bad)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "# Tarjan 算法求桥边模版\n",
    "class TarjanSCC:\n",
    "    def __init__(self, n: int, edges: List[List[int]], edgesId: List[List[int]]):\n",
    "        self.n = n\n",
    "        self.edges = edges\n",
    "        self.edgesId = edgesId\n",
    "        self.low = [-1] * n\n",
    "        self.dfn = [-1] * n\n",
    "        self.ans = list()\n",
    "        self.ts = -1\n",
    "    \n",
    "    def getCuttingEdge(self) -> List[int]:\n",
    "        for i in range(self.n):\n",
    "            if self.dfn[i] == -1:\n",
    "                self.pGetCuttingEdge(i, -1)\n",
    "        return self.ans\n",
    "    \n",
    "    def pGetCuttingEdge(self, u: int, parentEdgeId: int):\n",
    "        self.ts += 1\n",
    "        self.low[u] = self.dfn[u] = self.ts\n",
    "        for v, iden in zip(self.edges[u], self.edgesId[u]):\n",
    "            if self.dfn[v] == -1:\n",
    "                self.pGetCuttingEdge(v, iden)\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "                if self.low[v] > self.dfn[u]:\n",
    "                    self.ans.append(iden)\n",
    "            elif iden != parentEdgeId:\n",
    "                self.low[u] = min(self.low[u], self.dfn[v])\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "        ans0 = list()\n",
    "        label = [0] * m\n",
    "\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            # 找出所有权值为 w 的边，下标范围为 [i, j)\n",
    "            w = edges[i][2]\n",
    "            j = i\n",
    "            while j < m and edges[j][2] == edges[i][2]:\n",
    "                j += 1\n",
    "\n",
    "            # 存储每个连通分量在图 G 中的编号\n",
    "            compToId = dict()\n",
    "            # 图 G 的节点数\n",
    "            gn = 0\n",
    "            \n",
    "            for k in range(i, j):\n",
    "                x = uf.findset(edges[k][0])\n",
    "                y = uf.findset(edges[k][1])\n",
    "                if x != y:\n",
    "                    if x not in compToId:\n",
    "                        compToId[x] = gn\n",
    "                        gn += 1\n",
    "                    if y not in compToId:\n",
    "                        compToId[y] = gn\n",
    "                        gn += 1\n",
    "                else:\n",
    "                    # 将自环边标记为 -1\n",
    "                    label[edges[k][3]] = -1\n",
    "            \n",
    "            # 图 G 的边\n",
    "            gm = collections.defaultdict(list)\n",
    "            gmid = collections.defaultdict(list)\n",
    "            \n",
    "            for k in range(i, j):\n",
    "                x = uf.findset(edges[k][0])\n",
    "                y = uf.findset(edges[k][1])\n",
    "                if x != y:\n",
    "                    idx, idy = compToId[x], compToId[y]\n",
    "                    gm[idx].append(idy)\n",
    "                    gmid[idx].append(edges[k][3])\n",
    "                    gm[idy].append(idx)\n",
    "                    gmid[idy].append(edges[k][3])\n",
    "\n",
    "            bridges = TarjanSCC(gn, gm, gmid).getCuttingEdge()\n",
    "            # 将桥边（关键边）标记为 1\n",
    "            ans0.extend(bridges)\n",
    "            for iden in bridges:\n",
    "                label[iden] = 1\n",
    "\n",
    "            for k in range(i, j):\n",
    "                uf.unite(edges[k][0], edges[k][1])\n",
    "            \n",
    "            i = j\n",
    "\n",
    "        # 未标记的边即为非桥边（伪关键边）\n",
    "        ans1 = [i for i in range(m) if label[i] == 0]\n",
    "\n",
    "        return [ans0, ans1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.cnt = n\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.fa[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.fa[i] = self.find(self.fa[i])\n",
    "            return self.fa[i]\n",
    "\n",
    "    def merge(self, i, j):\n",
    "        fi = self.find(i)\n",
    "        fj = self.find(j)\n",
    "\n",
    "        if fi == fj:\n",
    "            return False\n",
    "        else:\n",
    "            self.fa[fi] = fj\n",
    "            self.cnt -= 1\n",
    "            return True\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "\n",
    "        for i, e in enumerate(edges):\n",
    "            e.append(i)\n",
    "\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "        values = 0\n",
    "        for a, b, w, i in edges:\n",
    "            if uf.merge(a, b):\n",
    "                values += w\n",
    "\n",
    "        ret1 = []\n",
    "        for i in range(m):\n",
    "            ufi = UnionFind(n)\n",
    "            vi = 0\n",
    "\n",
    "            for j in range(m):\n",
    "                if j != i:\n",
    "                    a, b, w, k = edges[j]\n",
    "\n",
    "                    if ufi.merge(a, b):\n",
    "                        vi += w\n",
    "\n",
    "            if ufi.cnt != 1 or (vi > values):\n",
    "                ret1.append(edges[i][3])\n",
    "            \n",
    "        ret2 = []\n",
    "        for i in range(m):\n",
    "            if edges[i][3] in ret1:\n",
    "                continue\n",
    "\n",
    "            ufi = UnionFind(n)\n",
    "            a, b, w, k = edges[i]\n",
    "            ufi.merge(a, b)\n",
    "\n",
    "            vi = w\n",
    "            for j in range(m):\n",
    "                if j != i:\n",
    "                    a, b, w, k = edges[j]\n",
    "                    if ufi.merge(a, b):\n",
    "                        vi += w\n",
    "\n",
    "            if vi == values:\n",
    "                ret2.append(edges[i][3])\n",
    "\n",
    "        return ret1, ret2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        father=[0]*n\n",
    "        def find(x):\n",
    "            if x==father[x]:\n",
    "                return x\n",
    "            father[x]=find(father[x])\n",
    "            return father[x]\n",
    "        def unoin(a,b):\n",
    "            father[find(a)]=find(b)\n",
    "        def kruskal(e):\n",
    "            tpl=[]\n",
    "            for a,b,c in e:\n",
    "                tpl.append([c,a,b])\n",
    "            tpl.sort()\n",
    "            for i in range(n):\n",
    "                father[i]=i\n",
    "            i,count=0,0\n",
    "            m=len(e)\n",
    "            dis=0\n",
    "            while i<m and count<n-1:\n",
    "                c,a,b =tpl[i]\n",
    "                if find(a)!=find(b):\n",
    "                    unoin(a,b)\n",
    "                    dis+=c\n",
    "                    count+=1\n",
    "                i+=1\n",
    "            return dis if count==n-1 else -1\n",
    "        tmp=kruskal(edges)\n",
    "        a1=[]\n",
    "        a2=[]\n",
    "        a3=[]\n",
    "        for i in range(len(edges)):\n",
    "            tpe=list(edges)\n",
    "            tpe.pop(i)\n",
    "            tmp0=kruskal(tpe)\n",
    "            if tmp0==tmp:\n",
    "                a2.append(i)\n",
    "            else:\n",
    "                a1.append(i)\n",
    "        for i in a2:\n",
    "            tpe=list(edges)\n",
    "            a,b,c=edges[i]\n",
    "            tpe.append([a,b,0])\n",
    "            tmp1=kruskal(tpe)+c\n",
    "            if tmp1==tmp :\n",
    "                a3.append(i)\n",
    "        #print(a1,a2,a3)\n",
    "        return[a1,a3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data = [i for i in range(n)] \n",
    "        self.setcount = n  \n",
    "    def find(self, x):\n",
    "        if self.data[x] == x:\n",
    "            return x \n",
    "        else:\n",
    "            self.data[x] = self.find(self.data[x]) \n",
    "            return self.data[x] \n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] = fx  \n",
    "            self.setcount -= 1 \n",
    "            return True \n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        dsu = DSU(n)\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x : x[2]) \n",
    "       \n",
    "        value = 0 \n",
    "        for i in range(m):\n",
    "            if dsu.un(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2] \n",
    "        \n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        for i in range(m):\n",
    "            dsu1 = DSU(n) \n",
    "            v1 = 0 \n",
    "            for j in range(m):\n",
    "                if i != j and dsu1.un(edges[j][0], edges[j][1]):\n",
    "                    v1 += edges[j][2]\n",
    "            \n",
    "            if dsu1.setcount != 1 or (dsu1.setcount == 1 and v1 > value):\n",
    "                ans1.append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            dsu2 = DSU(n) \n",
    "            dsu2.un(edges[i][0], edges[i][1])\n",
    "            v2 = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and dsu2.un(edges[j][0], edges[j][1]):\n",
    "                    v2 += edges[j][2]\n",
    "            \n",
    "            if v2 == value:\n",
    "                ans2.append(edges[i][3])\n",
    "            \n",
    "        return [ans1, ans2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def find(parent,x):\n",
    "            while parent[x] !=x:\n",
    "                x = parent[x]\n",
    "            return x \n",
    "        def union(parent,cnt,x,y):\n",
    "            px,py = find(parent,x),find(parent,y)\n",
    "            if px==py:return False\n",
    "            elif px<py:\n",
    "                parent[py]= px \n",
    "                cnt[px]+=cnt[py]\n",
    "            else:\n",
    "                parent[px]=py \n",
    "                cnt[py] += cnt[px]\n",
    "            return True\n",
    "        m = len(edges)\n",
    "        parent = list(range(n))\n",
    "        idx= list(range(m))\n",
    "        idx.sort(key=lambda x:edges[x][2])\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        cnt = [1]*n\n",
    "        rec = 0\n",
    "        for a,b,c in edges:\n",
    "            if union(parent,cnt,a,b):\n",
    "                rec+=c \n",
    "            if cnt[0]==n:\n",
    "                break \n",
    "\n",
    "        imp,nimp =[],[]\n",
    "        for i in range(m):\n",
    "            parentmp1=list(range(n))\n",
    "            cntmp1 = [1]*n\n",
    "            tmp1= 0\n",
    "            for j in range(m):\n",
    "                if j!=i and union(parentmp1,cntmp1,edges[j][0],edges[j][1]):\n",
    "                    tmp1+=edges[j][2]\n",
    "            if cntmp1[0]!=n or tmp1>rec:\n",
    "                imp.append(idx[i])\n",
    "            else:\n",
    "                parentmp2=list(range(n))\n",
    "                cntmp2 = [1]*n\n",
    "                tmp2 = edges[i][2]\n",
    "                union(parentmp2,cntmp2,edges[i][0],edges[i][1])\n",
    "                for j in range(m):\n",
    "                    if j!=i and union(parentmp2,cntmp2,edges[j][0],edges[j][1]):\n",
    "                        tmp2+=edges[j][2]\n",
    "                if cntmp2[0] ==n and tmp2==rec:\n",
    "                    nimp.append(idx[i])\n",
    "        return [imp,nimp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if self.rank[rx] < self.rank[ry]:\n",
    "            rx, ry = ry, rx\n",
    "        self.parent[ry] = rx\n",
    "        self.rank[rx] += ry\n",
    "\n",
    "    def connected(self, x ,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        ind = sorted(range(len(edges)), key=lambda x:edges[x][2])\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        ans = [[], []]\n",
    "        min_cost = self.kruskal(n, edges)\n",
    "        for i in range(len(edges)):\n",
    "            skip = edges[i]\n",
    "            new_edges = edges[:i] + edges[i+1:]\n",
    "            if self.kruskal(n, new_edges) > min_cost:\n",
    "                ans[0].append(ind[i])\n",
    "            elif self.kruskal(n, new_edges, skip) == min_cost:\n",
    "                ans[1].append(ind[i])\n",
    "        return ans\n",
    "\n",
    "    \n",
    "    def kruskal(self, n, edges, skip=None):\n",
    "        uf = UnionFind(n)\n",
    "        cost = 0\n",
    "        cnt = 0\n",
    "        if skip:\n",
    "            u, v, w = skip\n",
    "            uf.union(u, v)\n",
    "            cost += w\n",
    "            cnt += 1\n",
    "        for u, v, w in edges:\n",
    "            if uf.connected(u, v): continue\n",
    "            uf.union(u, v)\n",
    "            cost += w\n",
    "            cnt += 1\n",
    "            if cnt == n - 1:\n",
    "                break\n",
    "        return cost if cnt == n-1 else inf\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        self.parent[y] = x\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        root = list(range(n))\n",
    "        def Find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = Find(root[x])\n",
    "            return root[x]\n",
    "        def Union(x,y):\n",
    "            root[x] = y\n",
    "\n",
    "        sorted_edges = [[index] + i for index,i in enumerate(edges)]\n",
    "        sorted_edges.sort(key = lambda x : x[-1])\n",
    "        min_cost = 0\n",
    "        for [_,x,y,w] in sorted_edges:\n",
    "            rx,ry = Find(x),Find(y)\n",
    "            if rx != ry:\n",
    "                min_cost += w\n",
    "                Union(rx,ry)\n",
    "\n",
    "        key_edge = []\n",
    "        pseudo_key_edge = []\n",
    "        for i,edge in enumerate(sorted_edges):\n",
    "            (idx,x,y,w) = edge\n",
    "            tmp_edges = sorted_edges[:i] + sorted_edges[i + 1:]\n",
    "\n",
    "            total1 = w\n",
    "            root = list(range(n))\n",
    "            Union(x,y)\n",
    "            for i,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx,ry = Find(x),Find(y)\n",
    "                if rx != ry:\n",
    "                    Union(rx,ry)\n",
    "                    total1 += w\n",
    "            if total1 != min_cost:continue\n",
    "\n",
    "            total2 = 0\n",
    "            root = list(range(n))\n",
    "            for i,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx,ry = Find(x),Find(y)\n",
    "                if rx != ry:\n",
    "                    Union(rx,ry)\n",
    "                    total2 += w\n",
    "            if total1 != total2:\n",
    "                key_edge.append(idx)\n",
    "            else:\n",
    "                pseudo_key_edge.append(idx)\n",
    "        return [key_edge,pseudo_key_edge]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i in range(m):\n",
    "            edges[i].append(i)\n",
    "        \n",
    "        # 根据权值进行排序\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "        \n",
    "        def find(i, parent):\n",
    "            if i != parent[i]:\n",
    "                parent[i] = find(parent[i], parent)\n",
    "            return parent[i]\n",
    "        \n",
    "        def kruskal(avoid=-1, use=-1):\n",
    "            parent = [i for i in range(n)]\n",
    "            weight = 0\n",
    "            count = 0\n",
    "            \n",
    "            if use != -1:\n",
    "                weight += edges[use][2]\n",
    "                u, v = find(edges[use][0], parent), find(edges[use][1], parent)\n",
    "                if u != v:\n",
    "                    parent[u] = v\n",
    "                    count += 1\n",
    "                \n",
    "            for i in range(m):\n",
    "                if i == avoid or i == use:\n",
    "                    continue\n",
    "                u, v = find(edges[i][0], parent), find(edges[i][1], parent)\n",
    "                if u != v:\n",
    "                    parent[u] = v\n",
    "                    weight += edges[i][2]\n",
    "                    count += 1\n",
    "            \n",
    "            return weight if count == n - 1 else float('inf')\n",
    "        \n",
    "        base = kruskal() # 基准权值\n",
    "        critical, non_critical = [], []\n",
    "        \n",
    "        for i in range(m):\n",
    "            if kruskal(i) > base:\n",
    "                critical.append(edges[i][3])\n",
    "            elif kruskal(-1, i) == base:\n",
    "                non_critical.append(edges[i][3])\n",
    "                \n",
    "        return [critical, non_critical]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.comp_cnt = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1 for _ in range(n)]\n",
    "    def find(self,x):\n",
    "        return x if self.fa[x]==x else self.find(self.fa[x])\n",
    "    def union(self,x,y)->bool:\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x]<self.sz[y]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "        self.comp_cnt-=1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i,edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "\n",
    "        uf = UF(n)\n",
    "        value = 0\n",
    "        for x,y,w,i in edges:\n",
    "            if uf.union(x,y):\n",
    "                value+=w\n",
    "        # print(value)\n",
    "        ans = [[],[]]\n",
    "        for i in range(m):\n",
    "\n",
    "            uf = UF(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            # print(v,edges[i])\n",
    "            if uf.comp_cnt!=1 or (uf.comp_cnt == 1 and v>value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = UF(n)\n",
    "            v = edges[i][2]\n",
    "            uf.union(edges[i][0],edges[i][1])\n",
    "            for j in range(m):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if uf.union(edges[j][0],edges[j][1]):\n",
    "                    v+=edges[j][2]\n",
    "            # print(2222,v,edges[i])\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def find(parent,x):\n",
    "            while parent[x] != x:\n",
    "                x = parent[x]\n",
    "            return x\n",
    "        def union(parent,cnt,x,y):\n",
    "            px,py = find(parent,x),find(parent,y)\n",
    "            if px==py:\n",
    "                return False \n",
    "            elif py<px:\n",
    "                px,py = py,px \n",
    "            parent[py] = px \n",
    "            cnt[px] += cnt[py]\n",
    "            return True\n",
    "        \n",
    "        m = len(edges)\n",
    "        parent = list(range(n))\n",
    "        cnt = [1]*n\n",
    "        idx = list(range(m))\n",
    "        idx.sort(key = lambda x:edges[x][2])\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        rec = 0\n",
    "        for a,b,c in edges:\n",
    "            if union(parent,cnt,a,b):\n",
    "                rec+=c\n",
    "            if cnt[0] == n:\n",
    "                break\n",
    "        \n",
    "        imp=[]\n",
    "        nimp = []\n",
    "        \n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            parenttest = list(range(n))\n",
    "            cnttest = [1]*n\n",
    "            for j in range(m):\n",
    "                if j==i: continue\n",
    "                a,b,c = edges[j]\n",
    "                if union(parenttest,cnttest,a,b):\n",
    "                    tmp+=c\n",
    "                if cnttest[0] ==n:\n",
    "                    break \n",
    "            if tmp>rec or cnttest[0]!=n:\n",
    "                imp.append(idx[i])\n",
    "                continue\n",
    "            \n",
    "            parenttest1 = list(range(n))\n",
    "            cnttest1 = [1]*n\n",
    "            tmp1 = edges[i][2]\n",
    "            union(parenttest1,cnttest1,edges[i][0],edges[i][1])\n",
    "            for j in range(m):\n",
    "                if j==i: continue\n",
    "                a,b,c = edges[j]\n",
    "                if union(parenttest1,cnttest1,a,b):\n",
    "                    tmp1+=c\n",
    "                if cnttest1[0] ==n:\n",
    "                    break\n",
    "            if tmp1==rec:\n",
    "                nimp.append(idx[i])\n",
    "        return [imp,nimp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(x, parent):\n",
    "    if x != parent[x]:\n",
    "        parent[x] = find(parent[x], parent)\n",
    "    return parent[x]\n",
    "\n",
    "def union(x, y, parent):\n",
    "    px, py = find(x, parent), find(y, parent)\n",
    "    if px == py:\n",
    "        return False\n",
    "    parent[px] = py\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def kruskal(rm, parent, mst_w, k):\n",
    "            for start, end, w in sorted(edges, key=lambda x: x[2]):\n",
    "                edge = [start, end, w]\n",
    "                if edge == rm:\n",
    "                    continue\n",
    "                if union(start, end, parent):\n",
    "                    mst_w += w\n",
    "                    k += 1\n",
    "            return mst_w if k == n else inf\n",
    "        res = [[], []]\n",
    "        mst_w = kruskal(None, [*range(n)], 0, 1)\n",
    "        for i, edge in enumerate(edges):\n",
    "            rm_w = kruskal(edge, [*range(n)], 0, 1)\n",
    "            if rm_w > mst_w:\n",
    "                res[0].append(i)\n",
    "            else:\n",
    "                parent = [*range(n)]\n",
    "                parent[edge[0]] = edge[1]\n",
    "                if kruskal(edge, parent, edge[2], 2) == mst_w:\n",
    "                    res[1].append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "\n",
    "    def __init__(self, n):\n",
    "\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x == y:return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.parent[y] = x\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m = len(edges)\n",
    "\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        # 最小\n",
    "        edges.sort(key = lambda x: x[2])\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            if uf_std.union(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        res = [[], []]\n",
    "\n",
    "        for i in range(m):\n",
    "\n",
    "            uf = UnionFind(n)\n",
    "\n",
    "            v = 0\n",
    "\n",
    "            for j in range(m):\n",
    "                if i != j and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                res[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = UnionFind(n)\n",
    "            uf.union(edges[i][0], edges[i][1])\n",
    "\n",
    "            v = edges[i][2]\n",
    "\n",
    "            for j in range(m):\n",
    "\n",
    "                if i != j and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                res[1].append(edges[i][3])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        father=[0]*n\n",
    "        def find(x):\n",
    "            if x==father[x]:\n",
    "                return x\n",
    "            father[x]=find(father[x])\n",
    "            return father[x]\n",
    "        def unoin(a,b):\n",
    "            father[find(a)]=find(b)\n",
    "        def kruskal(e):\n",
    "            tpl=[]\n",
    "            for a,b,c in e:\n",
    "                tpl.append([c,a,b])\n",
    "            tpl.sort()\n",
    "            for i in range(n):\n",
    "                father[i]=i\n",
    "            i,count=0,0\n",
    "            m=len(e)\n",
    "            dis=0\n",
    "            while i<m and count<n-1:\n",
    "                c,a,b =tpl[i]\n",
    "                if find(a)!=find(b):\n",
    "                    unoin(a,b)\n",
    "                    dis+=c\n",
    "                    count+=1\n",
    "                i+=1\n",
    "            return dis if count==n-1 else -1\n",
    "        tmp=kruskal(edges)\n",
    "        a1=[]\n",
    "        a2=[]\n",
    "        a3=[]\n",
    "        for i in range(len(edges)):\n",
    "            tpe=list(edges)\n",
    "            tpe.pop(i)\n",
    "            tmp0=kruskal(tpe)\n",
    "            if tmp0==tmp:\n",
    "                a2.append(i)\n",
    "            else:\n",
    "                a1.append(i)\n",
    "        for i in a2:\n",
    "            tpe=list(edges)\n",
    "            a,b,c=edges[i]\n",
    "            tpe.append([a,b,0])\n",
    "            tmp1=kruskal(tpe)+c\n",
    "            if tmp1==tmp :\n",
    "                a3.append(i)\n",
    "        #print(a1,a2,a3)\n",
    "        return[a1,a3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, n):\n",
    "        while n != self.parent[n]:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if self.rank[p1] > self.rank[p2]:\n",
    "            self.parent[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "        else:\n",
    "            self.parent[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "        uf, mst_weight = UF(n), 0 # get mst weight\n",
    "        for u, v, w, i in edges:\n",
    "            if uf.find(u) != uf.find(v):\n",
    "                uf.union(u, v)\n",
    "                mst_weight += w\n",
    "\n",
    "        res = [[], []] # critical pseudo\n",
    "        for u1, v1, w1, i in edges:\n",
    "            weight = 0 # without curr edge\n",
    "            uf = UF(n)\n",
    "            for u2, v2, w2, j in edges:\n",
    "                if i != j and uf.find(u2) != uf.find(v2):\n",
    "                    uf.union(u2, v2)\n",
    "                    weight += w2\n",
    "            # can cause more than 1 connected component\n",
    "            if max(uf.rank) != n or weight > mst_weight: \n",
    "                res[0].append(i)\n",
    "                continue\n",
    "\n",
    "            uf, weight = UF(n), w1 # without curr edge\n",
    "            uf.union(u1, v1)\n",
    "            for u2, v2, w2, j in edges:\n",
    "                if uf.find(u2) != uf.find(v2):\n",
    "                    uf.union(u2, v2)\n",
    "                    weight += w2\n",
    "            if weight == mst_weight:\n",
    "                res[1].append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        root = list(range(n))\n",
    "        def Find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = Find(root[x])\n",
    "            return root[x]\n",
    "        def Union(x,y):\n",
    "            root[x] = y\n",
    "\n",
    "        sorted_edges = [[index] + i for index,i in enumerate(edges)]\n",
    "        sorted_edges.sort(key = lambda x : x[-1])\n",
    "        min_cost = 0\n",
    "        for [_,x,y,w] in sorted_edges:\n",
    "            rx,ry = Find(x),Find(y)\n",
    "            if rx != ry:\n",
    "                min_cost += w\n",
    "                Union(rx,ry)\n",
    "\n",
    "        key_edge = []\n",
    "        pseudo_key_edge = []\n",
    "        for i,edge in enumerate(sorted_edges):\n",
    "            (_,x,y,w) = edge\n",
    "            tmp_edges = sorted_edges[:i] + sorted_edges[i + 1:]\n",
    "\n",
    "            total1 = w\n",
    "            root = list(range(n))\n",
    "            Union(x,y)\n",
    "            for idx,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx,ry = Find(x),Find(y)\n",
    "                if rx != ry:\n",
    "                    Union(rx,ry)\n",
    "                    total1 += w\n",
    "            if total1 != min_cost:continue\n",
    "\n",
    "            total2 = 0\n",
    "            root = list(range(n))\n",
    "            for idx,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx,ry = Find(x),Find(y)\n",
    "                if rx != ry:\n",
    "                    Union(rx,ry)\n",
    "                    total2 += w\n",
    "            if total1 != total2:\n",
    "                key_edge.append(edge[0])\n",
    "            else:\n",
    "                pseudo_key_edge.append(edge[0])\n",
    "        return [key_edge,pseudo_key_edge]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        #解题思路：\n",
    "        #并查集，Kruskal算法\n",
    "        #每次权值相同、可以连接的两条边是伪关键边\n",
    "        #解析：只需要枚举每一条边，并用略微修改的 Kruskal算法判断其是否是关键边或伪关键边\n",
    "        #理解什么是关键边：\n",
    "        #如果最小生成树中删去某条边，会导致最小生成树的权值和增加，或者无法生成最小生成树，这条边就是关键边\n",
    "        #伪关键边：去掉后对最小生成树没有影响,但可能会在最小生成树的路径中\n",
    "\n",
    "        m = len(edges)\n",
    "        for i,edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key = lambda x : x[2])\n",
    "    \n",
    "        value = 0 #最小生成树的权值\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(m):\n",
    "            if uf.union(edges[i][0],edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        res = [[],[]]\n",
    "        for i in range(m):\n",
    "            #判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.part != 1 or (uf.part == 1 and v > value):\n",
    "                # print(i,uf.part,v,value)\n",
    "                res[0].append(edges[i][3])\n",
    "                continue\n",
    "           \n",
    "            #判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = edges[i][2]\n",
    "            uf.union(edges[i][0],edges[i][1])\n",
    "            for j in range(m):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.part == 1 and v == value:\n",
    "                res[1].append(edges[i][3])\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "\n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        while root != self.root[root]:\n",
    "            root = self.root[root]\n",
    "        while x != root:\n",
    "            father_x = self.root[x]\n",
    "            self.root[x] = root\n",
    "            x = father_x\n",
    "        return x\n",
    "\n",
    "    def union(self,x,y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x,root_y = root_y,root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.size[root_x] == 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        parent = list(range(n))\n",
    "\n",
    "        def find(index):\n",
    "            if index != parent[index]:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            parent[index2] = index1\n",
    "\n",
    "        sorted_edges = [[index]+i for index, i in enumerate(edges)]\n",
    "        sorted_edges = sorted(sorted_edges, key=lambda x:x[-1])\n",
    "\n",
    "        total = 0\n",
    "        for index, (_, x, y, w) in enumerate(sorted_edges):\n",
    "            rx, ry = find(x), find(y)\n",
    "\n",
    "            if rx != ry:\n",
    "                union(rx, ry)\n",
    "                total += w\n",
    "        \n",
    "        key_edge = []\n",
    "        not_key_edge = []\n",
    "\n",
    "        for i, edge in enumerate(sorted_edges):\n",
    "            (_,cx,cy,cw) = edge\n",
    "            # 去掉当前边, 形成新的边列表\n",
    "            tmp_edges = sorted_edges[:i]+sorted_edges[i+1:]\n",
    "\n",
    "            total1 = cw\n",
    "            parent=list(range(n))\n",
    "            union(cx,cy)\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx, ry = find(x), find(y)\n",
    "                if rx!=ry:\n",
    "                    union(rx, ry)\n",
    "                    total1 += w\n",
    "\n",
    "            if total != total1:\n",
    "                continue\n",
    "\n",
    "            total2 = 0\n",
    "            parent=list(range(n))\n",
    "\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx, ry = find(x), find(y)\n",
    "                if rx!=ry:\n",
    "                    union(rx, ry)\n",
    "                    total2 += w\n",
    "\n",
    "            if total1 != total2:\n",
    "                key_edge.append(edge[0])\n",
    "            else:\n",
    "                not_key_edge.append(edge[0])\n",
    "        \n",
    "        return[key_edge, not_key_edge]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        parent=list(range(n))\n",
    "        def find(index):\n",
    "            if index!=parent[index]:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        def union(index1, index2):\n",
    "            parent[index2] = index1\n",
    "            \n",
    "        # 这里由小到大排序 就是 Kruskal 的思想\n",
    "        # 在原有的edge中添加位置索引，方便排序后能得到在原edges中的位置\n",
    "        sorted_edges = [[index]+i for index, i in enumerate(edges)]\n",
    "        # 根据 weight 对边进行排序\n",
    "        sorted_edges = sorted(sorted_edges, key=lambda x:x[-1])\n",
    "\n",
    "\n",
    "        # 计算最小生成树的权值和 total\n",
    "        total = 0\n",
    "        for index,(_,x,y,w) in enumerate(sorted_edges):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx!=ry:\n",
    "                union(rx, ry)\n",
    "                total+=w\n",
    "\n",
    "\n",
    "\n",
    "        # 接下来 进行 最小生成树的构造 分为两种情况：\n",
    "        # 1.先连接当前边，得到所有连通边的权值和 total1\n",
    "        # 若 total与total1 相等，则代表 该边为有效边， 否则为无效边直接跳过\n",
    "        # 2.去掉当前边，得到所有连通边的权值和 total2\n",
    "        # 若 total1不等于total2，则代表该边为 关键边， 否则为 防关键边\n",
    "\n",
    "        key_edge=[]  # 关键边列表\n",
    "        no_key_edge=[] # 非关键边列表\n",
    "        for i,edge in enumerate(sorted_edges):\n",
    "            (_,cx,cy,cw) = edge\n",
    "            # 去掉当前边, 形成新的边列表\n",
    "            tmp_edges = sorted_edges[:i]+sorted_edges[i+1:]\n",
    "            \n",
    "            \n",
    "\n",
    "            # 1.先连接当前边，得到连通边的权值和 total1\n",
    "            total1 = cw\n",
    "            parent=list(range(n))\n",
    "            union(cx,cy)\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                    rx, ry = find(x), find(y)\n",
    "                    if rx!=ry:\n",
    "                        union(rx, ry)\n",
    "                        total1+=w\n",
    "\n",
    "            # 若 total与total1 相等，则代表 该边为有效边， 否则为无效边直接跳过\n",
    "            if total!=total1:continue\n",
    "\n",
    "            # 2.去掉当前边，得到连通边的权值和 total2\n",
    "            total2 = 0\n",
    "            parent=list(range(n))\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                    rx, ry = find(x), find(y)\n",
    "                    if rx!=ry:\n",
    "                        union(rx, ry)\n",
    "                        total2+=w\n",
    "\n",
    " \n",
    "            # 若 total1不等于total2，则代表该边为 关键边， 否则为 伪关键边\n",
    " \n",
    "            if total1!=total2:\n",
    "                key_edge.append(edge[0])\n",
    "            else:\n",
    "                no_key_edge.append(edge[0])\n",
    "\n",
    "        return [key_edge,no_key_edge]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        parent = list(range(n))\n",
    "\n",
    "        def find(index):\n",
    "            if index != parent[index]:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            parent[index2] = index1\n",
    "\n",
    "        sorted_edges = [[index]+i for index, i in enumerate(edges)]\n",
    "        sorted_edges = sorted(sorted_edges, key=lambda x:x[-1])\n",
    "\n",
    "        total = 0\n",
    "        for index, (_, x, y, w) in enumerate(sorted_edges):\n",
    "            rx, ry = find(x), find(y)\n",
    "\n",
    "            if rx != ry:\n",
    "                union(rx, ry)\n",
    "                total += w\n",
    "        \n",
    "        key_edge = []\n",
    "        not_key_edge = []\n",
    "\n",
    "        for i, edge in enumerate(sorted_edges):\n",
    "            (_,cx,cy,cw) = edge\n",
    "            # 去掉当前边, 形成新的边列表\n",
    "            tmp_edges = sorted_edges[:i]+sorted_edges[i+1:]\n",
    "\n",
    "            total1 = cw\n",
    "            parent=list(range(n))\n",
    "            union(cx,cy)\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx, ry = find(x), find(y)\n",
    "                if rx!=ry:\n",
    "                    union(rx, ry)\n",
    "                    total1 += w\n",
    "\n",
    "            if total != total1:\n",
    "                continue\n",
    "\n",
    "            total2 = 0\n",
    "            parent=list(range(n))\n",
    "\n",
    "            for index,(_,x,y,w) in enumerate(tmp_edges):\n",
    "                rx, ry = find(x), find(y)\n",
    "                if rx!=ry:\n",
    "                    union(rx, ry)\n",
    "                    total2 += w\n",
    "\n",
    "            if total1 != total2:\n",
    "                key_edge.append(edge[0])\n",
    "            else:\n",
    "                not_key_edge.append(edge[0])\n",
    "        \n",
    "        return[key_edge, not_key_edge]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        # 计算 value\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.unite(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        ans = [list(), list()]\n",
    "        \n",
    "        for i in range(m):\n",
    "            # 判断是否是关键边\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 判断是否是伪关键边\n",
    "            uf = UnionFind(n)\n",
    "            uf.unite(edges[i][0], edges[i][1])\n",
    "            v = edges[i][2]\n",
    "            for j in range(m):\n",
    "                if i != j and uf.unite(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "      \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unionfind:\n",
    "    def __init__(self,n):\n",
    "        self.parent = list(range(n))\n",
    "        self.count = n\n",
    "        self.size = [1] *n\n",
    "    def find(self,x):\n",
    "        while self.parent[x] != x:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    def union(self,x,y):\n",
    "        rx,ry = self.find(x),self.find(y)\n",
    "        if rx == ry:\n",
    "            return False \n",
    "        if self.size[rx] < self.size[ry]:\n",
    "            rx,ry = rx,ry \n",
    "        self.parent[ry] = rx\n",
    "        self.size[rx] += self.size[ry]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "    \n",
    "            \n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        uf_mst = Unionfind(n)\n",
    "        for i,edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key = lambda x:x[2])\n",
    "        value = 0\n",
    "        for edge in edges:\n",
    "            if uf_mst.union(edge[0],edge[1]):\n",
    "                value += edge[2]\n",
    "        v = value\n",
    "        ans = [[],[]]\n",
    "\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            value = 0\n",
    "            uf = Unionfind(n)\n",
    "\n",
    "            for j in range(len(edges)):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    value += edges[j][2]\n",
    "            if uf.count != 1 or (uf.count == 1 and value > v):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = Unionfind(n)\n",
    "            value = edges[i][2]\n",
    "            uf.union(edges[i][0],edges[i][1])\n",
    "\n",
    "            for j in range(len(edges)):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    value += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n \n",
    "\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(\n",
    "        self, n: int, edges: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "\n",
    "        hashset = set() # 构成最小生成树的权重集合\n",
    "        ufs = UnionFindSet(n)\n",
    "\n",
    "        mst, cnt = 0, 1\n",
    "        for u, v, w in sorted(edges, key=lambda e: e[2]):\n",
    "            if ufs.find(u) != ufs.find(v):\n",
    "                ufs.union(u, v)\n",
    "                hashset.add(w)\n",
    "\n",
    "                mst += w\n",
    "                cnt += 1\n",
    "                if cnt == n:\n",
    "                    break\n",
    "\n",
    "        mst_edges = []\n",
    "        for i, (u, v, w) in enumerate(edges):\n",
    "            if w in hashset:\n",
    "                mst_edges.append((i, u, v, w))\n",
    "\n",
    "        res1, res2 = [], []\n",
    "\n",
    "        for idx, u, v, w in mst_edges:\n",
    "            ufs = UnionFindSet(n)\n",
    "            \n",
    "            heap = []\n",
    "            for i, (u, v, w) in enumerate(edges):\n",
    "                if i != idx:\n",
    "                    heappush(heap, (w, u, v))\n",
    "\n",
    "            vals, cnt = 0, 1\n",
    "            while heap and cnt < n:\n",
    "                val, u, v = heappop(heap)\n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "\n",
    "                    vals += val\n",
    "                    cnt += 1\n",
    "            \n",
    "            if cnt < n:\n",
    "                res1.append(idx)\n",
    "            else:\n",
    "                if vals == mst:\n",
    "                    res2.append(idx)\n",
    "                else:\n",
    "                    res1.append(idx)\n",
    "\n",
    "        res3 = []\n",
    "        for idx in res2:\n",
    "            ux, vx, wx = edges[idx]\n",
    "\n",
    "            es = sorted([(w, u, v) for i, (u, v, w) in enumerate(edges) if i != idx])\n",
    "            es = [(wx, ux, vx)] + es\n",
    "\n",
    "            ufs = UnionFindSet(n)\n",
    "\n",
    "            flag = True\n",
    "\n",
    "            vals, cnt = 0, 1\n",
    "            for w, u, v in es:\n",
    "                \n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "\n",
    "                    vals += w\n",
    "                    cnt += 1\n",
    "\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "            \n",
    "            if vals == mst:\n",
    "                res3.append(idx)\n",
    "\n",
    "        return [res1, res3]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.fa = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        fa = self.fa\n",
    "        if fa[x] != x:\n",
    "            fa[x] = self.find(fa[x])\n",
    "        return fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fa = self.fa\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        fa[y] = x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:\n",
    "\n",
    "        def kruskal(edges: list[list[int]], edge=None) -> int:\n",
    "            cnt = res = 0\n",
    "            uf = UnionFind(n)\n",
    "            if edge:\n",
    "                x, y, w = edge\n",
    "                uf.union(x, y)\n",
    "                res += w\n",
    "                cnt += 1\n",
    "            edges.sort(key=lambda x: x[2])\n",
    "            for x, y, weight in edges:\n",
    "                fx = uf.find(x)\n",
    "                fy = uf.find(y)\n",
    "                if fx != fy:\n",
    "                    res += weight\n",
    "                    uf.union(fx, fy)\n",
    "                    cnt += 1\n",
    "                if cnt == n - 1:\n",
    "                    break\n",
    "            return res\n",
    "\n",
    "        ret = kruskal(edges[:])\n",
    "\n",
    "        critical = list()\n",
    "        pseudo = list()\n",
    "        for i in range(len(edges)):\n",
    "            tmp = edges[:i] + edges[i + 1:]\n",
    "            ret1 = kruskal(tmp)\n",
    "            if ret1 != ret:\n",
    "                critical.append(i)\n",
    "            else:\n",
    "                ret2 = kruskal(tmp, edges[i])\n",
    "                if ret2 == ret:\n",
    "                    pseudo.append(i)\n",
    "                    \n",
    "        return [critical, pseudo]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(edges)\n",
    "        pa=list(range(n))\n",
    "        def query(i):\n",
    "            if pa[i]!=i: pa[i]=query(pa[i])\n",
    "            return pa[i]\n",
    "        def merge(i,j):\n",
    "            pa[query(i)]=query(j)\n",
    "        ch=[[] for _ in range(n)]\n",
    "        def cycle(u,t,m,pa):\n",
    "            res=[]\n",
    "            if u==t: return True,res\n",
    "            for v,w,i in ch[u]:\n",
    "                if v==pa: continue\n",
    "                able,tab=cycle(v,t,m,u)\n",
    "                if able:\n",
    "                    res.extend(tab)\n",
    "                    if w==m: res.append(i)\n",
    "                    return True,res\n",
    "            return False,res\n",
    "        vis=[0]*m\n",
    "        pq=[]\n",
    "        for i,(u,v,w) in enumerate(edges):\n",
    "            heappush(pq,(w,u,v,i))\n",
    "        cnt=n-1\n",
    "        pseudo=[0]*m\n",
    "        for _ in range(m):\n",
    "            w,u,v,i=heappop(pq)\n",
    "            vis[i]=1\n",
    "            if query(u)==query(v):\n",
    "                _,cc=cycle(u,v,w,-1)\n",
    "                if cc:\n",
    "                    pseudo[i]=1\n",
    "                    for j in cc: pseudo[j]=1\n",
    "                else: vis[i]=0\n",
    "            elif cnt:\n",
    "                merge(u,v)\n",
    "                ch[u].append((v,w,i))\n",
    "                ch[v].append((u,w,i))\n",
    "                cnt-=1\n",
    "            else: vis[i]=0\n",
    "        res=[[],[]]\n",
    "        for i in range(m):\n",
    "            if not vis[i]: continue\n",
    "            if pseudo[i]: res[1].append(i)\n",
    "            else: res[0].append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree\n",
    "class UnionFind:\n",
    "  def __init__(self, n: int):\n",
    "    self.id = list(range(n))\n",
    "    self.rank = [0] * n\n",
    "\n",
    "  def unionByRank(self, u: int, v: int) -> None:\n",
    "    i = self.find(u)\n",
    "    j = self.find(v)\n",
    "    if i == j:\n",
    "      return\n",
    "    if self.rank[i] < self.rank[j]:\n",
    "      self.id[i] = j\n",
    "    elif self.rank[i] > self.rank[j]:\n",
    "      self.id[j] = i\n",
    "    else:\n",
    "      self.id[i] = j\n",
    "      self.rank[j] += 1\n",
    "\n",
    "  def find(self, u: int) -> int:\n",
    "    if self.id[u] != u:\n",
    "      self.id[u] = self.find(self.id[u])\n",
    "    return self.id[u]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "    criticalEdges = []\n",
    "    pseudoCriticalEdges = []\n",
    "\n",
    "    # Record the index information, so edges[i] := (u, v, weight, index).\n",
    "    for i in range(len(edges)):\n",
    "      edges[i].append(i)\n",
    "\n",
    "    # Sort by weight.\n",
    "    edges.sort(key=lambda x: x[2])\n",
    "\n",
    "    def getMSTWeight(firstEdge: List[int], deletedEdgeIndex: int) -> Union[int, float]:\n",
    "      mstWeight = 0\n",
    "      uf = UnionFind(n)\n",
    "\n",
    "      if firstEdge:\n",
    "        uf.unionByRank(firstEdge[0], firstEdge[1])\n",
    "        mstWeight += firstEdge[2]\n",
    "\n",
    "      for u, v, weight, index in edges:\n",
    "        if index == deletedEdgeIndex:\n",
    "          continue\n",
    "        if uf.find(u) == uf.find(v):\n",
    "          continue\n",
    "        uf.unionByRank(u, v)\n",
    "        mstWeight += weight\n",
    "\n",
    "      root = uf.find(0)\n",
    "      if any(uf.find(i) != root for i in range(n)):\n",
    "        return math.inf\n",
    "\n",
    "      return mstWeight\n",
    "\n",
    "    mstWeight = getMSTWeight([], -1)\n",
    "\n",
    "    for edge in edges:\n",
    "      index = edge[3]\n",
    "      # Deleting `e` makes the MST weight increase or can't form a MST.\n",
    "      if getMSTWeight([], index) > mstWeight:\n",
    "        criticalEdges.append(index)\n",
    "      # If an edge can be in any MST, we can always add `edge` to the edge set.\n",
    "      elif getMSTWeight(edge, -1) == mstWeight:\n",
    "        pseudoCriticalEdges.append(index)\n",
    "\n",
    "    return [criticalEdges, pseudoCriticalEdges]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "\n",
    "    def __init__(self, n):\n",
    "\n",
    "        self.parent = list(range(n))\n",
    "\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x == y:return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.parent[y] = x\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m = len(edges)\n",
    "\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        # 最小\n",
    "        edges.sort(key = lambda x: x[2])\n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            if uf_std.union(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "\n",
    "        res = [[], []]\n",
    "\n",
    "        for i in range(m):\n",
    "\n",
    "            uf = UnionFind(n)\n",
    "\n",
    "            v = 0\n",
    "\n",
    "            for j in range(m):\n",
    "                if i != j and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount != 1 or (uf.setCount == 1 and v > value):\n",
    "                res[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = UnionFind(n)\n",
    "            uf.union(edges[i][0], edges[i][1])\n",
    "\n",
    "            v = edges[i][2]\n",
    "\n",
    "            for j in range(m):\n",
    "\n",
    "                if i != j and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if v == value:\n",
    "                res[1].append(edges[i][3])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unionfind:\n",
    "    def __init__(self,n):\n",
    "        self.parent = list(range(n))\n",
    "        self.count = n\n",
    "        self.size = [1] *n\n",
    "    def find(self,x):\n",
    "        while self.parent[x] != x:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    def union(self,x,y):\n",
    "        rx,ry = self.find(x),self.find(y)\n",
    "        if rx == ry:\n",
    "            return False \n",
    "        if self.size[rx] < self.size[ry]:\n",
    "            rx,ry = rx,ry \n",
    "        self.parent[ry] = rx\n",
    "        self.size[rx] += self.size[ry]\n",
    "        self.count -= 1\n",
    "        return True\n",
    "    \n",
    "            \n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        uf_mst = Unionfind(n)\n",
    "        for i,edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key = lambda x:x[2])\n",
    "        value = 0\n",
    "        for edge in edges:\n",
    "            if uf_mst.union(edge[0],edge[1]):\n",
    "                value += edge[2]\n",
    "        v = value\n",
    "        ans = [[],[]]\n",
    "\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            value = 0\n",
    "            uf = Unionfind(n)\n",
    "\n",
    "            for j in range(len(edges)):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    value += edges[j][2]\n",
    "            if uf.count != 1 or (uf.count == 1 and value > v):\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "            \n",
    "            uf = Unionfind(n)\n",
    "            value = edges[i][2]\n",
    "            uf.union(edges[i][0],edges[i][1])\n",
    "\n",
    "            for j in range(len(edges)):\n",
    "                if i != j and uf.union(edges[j][0],edges[j][1]):\n",
    "                    value += edges[j][2]\n",
    "            if v == value:\n",
    "                ans[1].append(edges[i][3])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n:int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1]*n\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "\n",
    "    def find(self, x:int):\n",
    "        while not x==self.parent[x]:\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.size[x]<self.size[y]:\n",
    "            x,y = y,x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.parent[y] = x\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x)==self.find(y)\n",
    "        \n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        # 在edges后面加上idx\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x:x[2])\n",
    "        \n",
    "        uf_std = UnionFind(n)\n",
    "        value = 0\n",
    "        for i in range(m):\n",
    "            if uf_std.union(edges[i][0], edges[i][1]):\n",
    "                value += edges[i][2]\n",
    "        \n",
    "        ans = [list(), list()]\n",
    "        for i in range(m):\n",
    "            #先判断是否是关键边（去掉第i个边，如果无法连通，或者代价v变大，那么是关键边）\n",
    "            uf = UnionFind(n)\n",
    "            v = 0\n",
    "            for j in range(m):\n",
    "                if j!=i and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v += edges[j][2]\n",
    "            if uf.setCount!=1 or v>value:\n",
    "                ans[0].append(edges[i][3])\n",
    "                continue\n",
    "\n",
    "            # 如果不是关键边，再判断是不是伪关键边。即将第i个边，直接首先进行合并，\n",
    "            # 如果这样得到的生成树代价v没有变大，那么这条边就是伪关键边\n",
    "            #（先判断关键边，是因为关键边也符合伪关键边的性质）\n",
    "            uf = UnionFind((n))\n",
    "            v = edges[i][2]\n",
    "            uf.union(edges[i][0], edges[i][1])\n",
    "            for j in range(m):\n",
    "                if j!=i and uf.union(edges[j][0], edges[j][1]):\n",
    "                    v+=edges[j][2]\n",
    "            if v==value:\n",
    "                ans[1].append(edges[i][3])\n",
    "            pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        edges = [[i]+v for i,v in enumerate(edges)]\n",
    "        edges.sort(key=lambda x:x[-1])\n",
    "\n",
    "        p={i:i for i in range(n)}\n",
    "        def find(x):\n",
    "            if p[x]==x:\n",
    "                return p[x]\n",
    "            p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def union(x,y):\n",
    "            p[find(x)]=find(y)\n",
    "      \n",
    "        def ksk(edg):\n",
    "            p={i:i for i in range(n)}\n",
    "            ans=0\n",
    "            for ind,s,e,d in edg:\n",
    "                a=find(s)\n",
    "                b=find(e)\n",
    "                if a!=b:\n",
    "                    ans=ans+d\n",
    "                    union(s,e)\n",
    "            return ans\n",
    "        good=[]\n",
    "        bad=[]\n",
    "        st=ksk(edges)\n",
    "     \n",
    "        for i in range(len(edges)):\n",
    "            ind,cs,ce,cw =edges[i]\n",
    "            p={j:j for j in range(n)}\n",
    "            union(cs,ce)\n",
    "            newe=edges[:i]+edges[i+1:]\n",
    "            x=ksk(newe)+cw\n",
    "            if st!=x:\n",
    "                continue\n",
    "            p={j:j for j in range(n)}\n",
    "            y=ksk(newe)\n",
    "            if st==y:\n",
    "                bad.append(ind)\n",
    "            else:\n",
    "                good.append(ind)\n",
    "        res=[]\n",
    "        res.append(good)\n",
    "        res.append(bad)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "# Tarjan 算法求桥边模版\n",
    "class TarjanSCC:\n",
    "    def __init__(self, n: int, edges: List[List[int]], edgesId: List[List[int]]):\n",
    "        self.n = n\n",
    "        self.edges = edges\n",
    "        self.edgesId = edgesId\n",
    "        self.low = [-1] * n\n",
    "        self.dfn = [-1] * n\n",
    "        self.ans = list()\n",
    "        self.ts = -1\n",
    "    \n",
    "    def getCuttingEdge(self) -> List[int]:\n",
    "        for i in range(self.n):\n",
    "            if self.dfn[i] == -1:\n",
    "                self.pGetCuttingEdge(i, -1)\n",
    "        return self.ans\n",
    "    \n",
    "    def pGetCuttingEdge(self, u: int, parentEdgeId: int):\n",
    "        self.ts += 1\n",
    "        self.low[u] = self.dfn[u] = self.ts\n",
    "        for v, iden in zip(self.edges[u], self.edgesId[u]):\n",
    "            if self.dfn[v] == -1:\n",
    "                self.pGetCuttingEdge(v, iden)\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "                if self.low[v] > self.dfn[u]:\n",
    "                    self.ans.append(iden)\n",
    "            elif iden != parentEdgeId:\n",
    "                self.low[u] = min(self.low[u], self.dfn[v])\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(edges)\n",
    "        for i, edge in enumerate(edges):\n",
    "            edge.append(i)\n",
    "        edges.sort(key=lambda x: x[2])\n",
    "\n",
    "        uf = UnionFind(n)\n",
    "        ans0 = list()\n",
    "        label = [0] * m\n",
    "\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            # 找出所有权值为 w 的边，下标范围为 [i, j)\n",
    "            w = edges[i][2]\n",
    "            j = i\n",
    "            while j < m and edges[j][2] == edges[i][2]:\n",
    "                j += 1\n",
    "\n",
    "            # 存储每个连通分量在图 G 中的编号\n",
    "            compToId = dict()\n",
    "            # 图 G 的节点数\n",
    "            gn = 0\n",
    "            \n",
    "            for k in range(i, j):\n",
    "                x = uf.findset(edges[k][0])\n",
    "                y = uf.findset(edges[k][1])\n",
    "                if x != y:\n",
    "                    if x not in compToId:\n",
    "                        compToId[x] = gn\n",
    "                        gn += 1\n",
    "                    if y not in compToId:\n",
    "                        compToId[y] = gn\n",
    "                        gn += 1\n",
    "                else:\n",
    "                    # 将自环边标记为 -1\n",
    "                    label[edges[k][3]] = -1\n",
    "            \n",
    "            # 图 G 的边\n",
    "            gm = collections.defaultdict(list)\n",
    "            gmid = collections.defaultdict(list)\n",
    "            \n",
    "            for k in range(i, j):\n",
    "                x = uf.findset(edges[k][0])\n",
    "                y = uf.findset(edges[k][1])\n",
    "                if x != y:\n",
    "                    idx, idy = compToId[x], compToId[y]\n",
    "                    gm[idx].append(idy)\n",
    "                    gmid[idx].append(edges[k][3])\n",
    "                    gm[idy].append(idx)\n",
    "                    gmid[idy].append(edges[k][3])\n",
    "\n",
    "            bridges = TarjanSCC(gn, gm, gmid).getCuttingEdge()\n",
    "            # 将桥边（关键边）标记为 1\n",
    "            ans0.extend(bridges)\n",
    "            for iden in bridges:\n",
    "                label[iden] = 1\n",
    "\n",
    "            for k in range(i, j):\n",
    "                uf.unite(edges[k][0], edges[k][1])\n",
    "            \n",
    "            i = j\n",
    "\n",
    "        # 未标记的边即为非桥边（伪关键边）\n",
    "        ans1 = [i for i in range(m) if label[i] == 0]\n",
    "\n",
    "        return [ans0, ans1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n \n",
    "\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(\n",
    "        self, n: int, edges: List[List[int]]\n",
    "    ) -> List[List[int]]:\n",
    "\n",
    "        # 1. 使用 Kruskal 算法求\n",
    "        #   - 最小生成树权值和\n",
    "        #   - 构成最小生成树的权值集合\n",
    "\n",
    "        # 最小生成树权值和\n",
    "        mstws = 0\n",
    "        # 构成最小生成树的权值集合\n",
    "        wset = set()\n",
    "\n",
    "        cnt = 1\n",
    "        ufs = UnionFindSet(n)\n",
    "\n",
    "        # Kruskal 算法\n",
    "        # 按边权值从小到大遍历所有边\n",
    "        for u, v, w in sorted(edges, key=lambda e: e[2]):\n",
    "            # 如果 (u, v) 为安全边，将其加入到最小生成树中\n",
    "            if ufs.find(u) != ufs.find(v):\n",
    "                ufs.union(u, v)\n",
    "                wset.add(w)\n",
    "                mstws += w\n",
    "\n",
    "                cnt += 1\n",
    "                if cnt == n:\n",
    "                    break\n",
    "\n",
    "        # 1. 根据构成最小生成树的权值集合 mstws 可得到\n",
    "        #    所有可能的关键边和伪关键边\n",
    "        \n",
    "        candset = set()\n",
    "        for i, edge in enumerate(edges):\n",
    "            if edge[-1] in wset:\n",
    "                candset.add(i)\n",
    "\n",
    "        # 3. 根据 Kruskal 算法找出所有关键边，其余的是可能的伪关键边\n",
    "        # 判断 (u, v) 是否为关键边的方法：去掉 (u, v)，剩余的边\n",
    "        #   - 如果不能得到生成树（图不连通），则 (u, v) 是关键边\n",
    "        #   - 如果得到的最小生成树权值和 > mstws，则 (u, v) 是关键边\n",
    "        #   - 否则，(u, v) 不是关键边 \n",
    "        \n",
    "        critical = []\n",
    "        for idx in candset:\n",
    "            # 设第 idx 条边为 (u, v)\n",
    "            \n",
    "            # heap 不包含第 idx 条边\n",
    "            heap = [(w, u, v) for i, (u, v, w) in enumerate(edges) if i != idx]\n",
    "            heapify(heap)\n",
    "            \n",
    "            ufs = UnionFindSet(n)\n",
    "\n",
    "            vals, cnt = 0, 1\n",
    "            while heap and cnt < n:\n",
    "                val, u, v = heappop(heap)\n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "                    vals += val\n",
    "                    cnt += 1\n",
    "            \n",
    "            if cnt < n or vals > mstws:\n",
    "                # cnt < n，说明去掉 (u, v)，图不连通，(u, v) 是关键边\n",
    "                # vals > mstws，去掉 (u, v)，最小生成树权值和增加，(u, v) 是关键边\n",
    "                critical.append(idx)\n",
    "\n",
    "        # 4. 根据所有可能的关键边和伪关键边集合 candset 和关键边集合 critical\n",
    "        #    得到所有可能的伪关键边集合 pcand = candset - critical\n",
    "\n",
    "        pcand = candset - set(critical)\n",
    "\n",
    "        print(candset, critical)\n",
    "\n",
    "        # 5. 使用 Kruskal 算法，验证所有可能的伪关键边是否为真正的伪关键边\n",
    "        # 判断候选伪关键边 (u, v) 是否为真正的伪关键边的方法是：\n",
    "        #   最先将 (u, v) 加入最小生成树，看最小生成树权值和是否等于 mstws\n",
    "        #   如果等于 mstws，说明 (u, v) 是真正的伪关键边，因为伪关键边是某棵最小生成树的边\n",
    "\n",
    "        pseudo = []\n",
    "        for idx in pcand:\n",
    "            # 设第 idx 条候选伪关键边为 (u, v)\n",
    "\n",
    "            ux, vx, wx = edges[idx]\n",
    "\n",
    "            # 去掉 (u, v)，对所有的边排序\n",
    "            edges_sorted = sorted([(w, u, v) for i, (u, v, w) in enumerate(edges) if i != idx])\n",
    "            \n",
    "            # 将 (u, v) 加入到 edges_sorted 前面\n",
    "            # 这样做的目的是，让 (u, v) 最先加入到最小生成树中\n",
    "            edges_sorted = [(wx, ux, vx)] + edges_sorted\n",
    "\n",
    "            ufs = UnionFindSet(n)\n",
    "\n",
    "            vals, cnt = 0, 1\n",
    "            for w, u, v in edges_sorted:\n",
    "                if ufs.find(u) != ufs.find(v):\n",
    "                    ufs.union(u, v)\n",
    "                    vals += w\n",
    "\n",
    "                    cnt += 1\n",
    "                    if cnt == n:\n",
    "                        break\n",
    "            \n",
    "            if vals == mstws:\n",
    "                pseudo.append(idx)\n",
    "\n",
    "        return [critical, pseudo]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def kruskal(rm, parent, mst_w, k):\n",
    "            def find(x):\n",
    "                if x != parent[x]:\n",
    "                    parent[x] = find(parent[x])\n",
    "                return parent[x]\n",
    "            def union(x, y):\n",
    "                px, py = find(x), find(y)\n",
    "                if px == py:\n",
    "                    return False\n",
    "                parent[px] = py\n",
    "                return True\n",
    "            for start, end, w in sorted(edges, key=lambda x: x[2]):\n",
    "                edge = [start, end, w]\n",
    "                if edge == rm:\n",
    "                    continue\n",
    "                if union(start, end):\n",
    "                    mst_w += w\n",
    "                    k += 1\n",
    "            return mst_w if k == n else inf\n",
    "        \n",
    "        res = [[], []]\n",
    "        mst_w = kruskal(None, [*range(n)], 0, 1)\n",
    "        for i, edge in enumerate(edges):\n",
    "            rm_w = kruskal(edge, [*range(n)], 0, 1)\n",
    "            if rm_w > mst_w:\n",
    "                res[0].append(i)\n",
    "            else:\n",
    "                parent = [*range(n)]\n",
    "                parent[edge[0]] = edge[1]\n",
    "                if kruskal(edge, parent, edge[2], 2) == mst_w:\n",
    "                    res[1].append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def getvalue(pos, r = 0):\n",
    "            ref = [i for i in range(n)]\n",
    "            def find(x):\n",
    "                if ref[x] != x:\n",
    "                    ref[x] = find(ref[x])\n",
    "                return ref[x]\n",
    "            heaq = []\n",
    "            for i in range(len(edges)):\n",
    "                if i != pos:\n",
    "                    heappush(heaq, (edges[i][2], edges[i][0], edges[i][1]))\n",
    "            res = r\n",
    "            if r:\n",
    "                ref[edges[pos][1]] = edges[pos][0]\n",
    "            while heaq:\n",
    "                val, x, y = heappop(heaq)\n",
    "                if find(x) != find(y):\n",
    "                    res += val\n",
    "                    ref[find(x)] = find(y)\n",
    "            for i in range(n):\n",
    "                ref[i] = find(i)\n",
    "            \n",
    "            return res if len(set(ref)) == 1 else float('inf')\n",
    "\n",
    "        v = getvalue(-1)\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        for i in range(len(edges)):\n",
    "            if getvalue(i) > v:\n",
    "                ans1.append(i)\n",
    "            else:\n",
    "                if getvalue(i, edges[i][2]) == v:\n",
    "                    ans2.append(i)\n",
    "        return [ans1, ans2]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        p=list(range(n))\n",
    "        def find(x):\n",
    "            if x!=p[x]:\n",
    "                p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def dfs(u,v,pw):\n",
    "            if u==v:\n",
    "                return True\n",
    "            visited.add(u)\n",
    "            for x, i in keyedge[u]:\n",
    "                w=edges[i][2]\n",
    "                if x not in visited and dfs(x,v,pw):\n",
    "                        if w==pw:\n",
    "                            k.discard(i)\n",
    "                            d.add(i)\n",
    "                            self.flag=True\n",
    "                        return True\n",
    "        weight=[]\n",
    "        for i,(u,v,w) in enumerate(edges):\n",
    "            weight.append((w,i))\n",
    "        keyedge=defaultdict(list)        \n",
    "        k,d=set(),set()\n",
    "        for w,i in sorted(weight):\n",
    "            u,v,_=edges[i]\n",
    "            pu,pv=find(u),find(v)\n",
    "            if pu!=pv:\n",
    "                p[pu] = find(pv)\n",
    "                keyedge[u].append((v,i))\n",
    "                keyedge[v].append((u,i))\n",
    "                k.add(i)\n",
    "            else:\n",
    "                visited=set()\n",
    "                self.flag=False\n",
    "                dfs(u,v,w)\n",
    "                if self.flag:\n",
    "                    d.add(i)\n",
    "        return list(k),list(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        p=list(range(n))\n",
    "        def find(x):\n",
    "            if x!=p[x]:\n",
    "                p[x]=find(p[x])\n",
    "            return p[x]\n",
    "        def dfs(u,v,pw):\n",
    "            if u==v:\n",
    "                return True\n",
    "            visited.add(u)\n",
    "            for x, i in keyedge[u]:\n",
    "                w=edges[i][2]\n",
    "                if x not in visited and dfs(x,v,pw):\n",
    "                        if w==pw:\n",
    "                            k.discard(i)\n",
    "                            d.add(i)\n",
    "                            self.flag=True\n",
    "                        return True\n",
    "        weight=[]\n",
    "        for i,(u,v,w) in enumerate(edges):\n",
    "            weight.append((w,i))\n",
    "        keyedge=defaultdict(list)        \n",
    "        k,d=set(),set()\n",
    "        for w,i in sorted(weight):\n",
    "            u,v,_=edges[i]\n",
    "            pu,pv=find(u),find(v)\n",
    "            if pu!=pv:\n",
    "                p[pu] = find(pv)\n",
    "                keyedge[u].append((v,i))\n",
    "                keyedge[v].append((u,i))\n",
    "                k.add(i)\n",
    "            else:\n",
    "                visited=set()\n",
    "                self.flag=False\n",
    "                dfs(u,v,w)\n",
    "                if self.flag:\n",
    "                    d.add(i)\n",
    "        return list(k),list(d)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
